package cn.yuemouren.map;

/**
 * @Author: Timi
 * @Description: 链表实现映射
 * @Date: 2020/6/22 8:56
 */
public class LinkedListMap<K,V> implements Map<K,V> {

    /**
     * 链表中节点类
     */
    private class Node{
        private K key;
        private V value;
        private Node next;

        public Node(){
            this(null);
        }

        public Node(K key){
            this(key,null);
        }

        public Node(K key,V value){
            this(key,value,null);
        }

        public Node(K key,V value,Node next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedListMap() {
        this.dummyHead = new Node();
        this.size = 0;
    }

    /**
     * 根据key获取节点
     * @param key
     * @return
     */
    private Node getNode(K key){
        Node cur = dummyHead;
        while(null != cur.next){
            if(key.equals(cur.next)){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    /**
     * 添加节点
     * @param key
     * @param value
     */
    @Override
    public void add(K key, V value) {
        Node cur = getNode(key);
        if(null == cur){
            dummyHead.next = new Node(key,value,dummyHead.next);
            size++;
        } else {
            cur.value = value;
        }
    }

    /**
     * 修改节点
     * @param key
     * @param newValue
     * @return
     */
    @Override
    public V set(K key, V newValue) {
        Node cur = getNode(key);
        if(null == cur){
            throw new IllegalArgumentException("节点不存在,无法修改");
        }
        V value = cur.value;
        cur.value = newValue;
        return value;
    }

    /**
     * 是否包含key
     * @param key
     * @return
     */
    @Override
    public boolean contain(K key) {
        return getNode(key) != null;
    }

    /**
     * 删除节点
     * @param key
     * @return
     */
    @Override
    public V remove(K key) {
        Node cur = dummyHead.next;
        Node delNode = null;
        while(null != cur){
            if(key.equals(cur.key)){
                break;
            }
            cur = cur.next;
        }
        if(null != cur){
            delNode = cur.next;
            cur = delNode.next;
            delNode.next = null;
            size--;
            return delNode.value;
        }
        return null;
    }

    /**
     * 获取size
     * @return
     */
    @Override
    public int getSize() {
        return size;
    }
}
